<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>linked list</title>
  </head>
  <body>
    <script>
      // 链表是一种链式存取的数据结构，
      // 用一组地址任意的存储单元存放线性表中的数据元素。
      // 链表中的基本数据以节点来表示，
      // 每个节点由元素+指针构成，
      // 元素是存储数据的存储单元，指针就是连接每个节点的地址数据
      // 双向列表有pre指针 两条链

      // 单向列表
      class Node {
        constructor(element) {
          this.element = element;
          this.next = null; // 初始化
        }
      }
      class LinkedList {
        constructor() {
          this.size = 0;
          this.head = null; // 头指针
        }
        // 根据索引获取
        getNode(index) {
          if (index < 0 || index >= this.size) {
            throw new Error("out range");
          }
          let current = this.head;
          // 找到最后一个指针
          for (var i = 0; i < index; i++) {
            current = current.next;
          }
          return current;
        }
        // 增加
        append(element) {
          // 将参数传入
          let node = new Node(element);
          // 列表为空
          if (this.head === null) {
            // head指向node实例节点
            this.head = node;
          } else {
            // 找到最后一位 最后一个索引
            let current = this.getNode(this.size - 1);
            current.next = node;
          }
          this.size++;
        }
        // 插入
        appendAt(position, element) {
          if (position < 0 || position > this.size) {
            throw new Error("out range");
          }
          let node = new Node(element);
          if (position === 0) {
            node.next = this.head; // 先把头部数据的next指向本身
            this.head = node; // 头指针还原
          } else {
            let pre = this.getNode(position - 1);
            node.next = pre.next;
            pre.next = node;
          }
          this.size++;
        }
        // 删除
        remove(position) {
          if (position < 0 || position > this.size) {
            throw new Error("out range");
          }
          let current = this.head;
          if (position === 0) {
            this.head = current.next;
          } else {
            let pre = this.getNode(position - 1);
            current = pre.next;
            pre.next = current.next;
          }
          this.size--;
        }
        // 查找
        indexOf(element) {
          let current = this.head;
          for (var i = 0; i < this, size; i++) {
            if (current.element === element) {
              return i;
            }
            current = current.next;
          }
          return -1; // 如果没找到
        }
      }

      let x = new LinkedList();
      x.append(1);
      x.append(2);
      x.append(3);
      // x.appendAt(4, 5);
      console.log(x, "@@@@@");
    </script>
  </body>
</html>
